﻿// Copyright (c) 2014 Morten Bakkedal
// This code is published under the MIT License.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace FuncLib.DualFunctions.Collections
{
	/// <summary>
	/// Minimalistic list class with fast Contains and IndexOf methods.
	/// </summary>
	[Serializable]
	[DebuggerDisplay("Count = {Count}")]
	public class HashedList<T> : IList<T>
	{
		private List<T> items;
		private Dictionary<T, int> indices;
		private int hashCode;

		public HashedList()
		{
			items = new List<T>();
			indices = new Dictionary<T, int>();
			hashCode = 23;
		}

		public void Add(T item)
		{
			items.Add(item);
			indices.Add(item, indices.Count); // lazy add to indices, i.e. if (indices != null) { add }

			unchecked
			{
				hashCode = hashCode * 31 + item.GetHashCode();
			}
		}

		public void AddOnce(T item)
		{
			if (!Contains(item))
			{
				Add(item);
			}
		}

		public bool Contains(T item)
		{
			return indices.ContainsKey(item);
		}

		public int IndexOf(T item)
		{
			int index;
			if (!indices.TryGetValue(item, out index))
			{
				index = -1;
			}

			return index;
		}

		public void Insert(int index, T item)
		{
			throw new InvalidOperationException();
		}

		public bool Remove(T item)
		{
			throw new InvalidOperationException();
		}

		public void RemoveAt(int index)
		{
			throw new InvalidOperationException();
		}

		public void Clear()
		{
			throw new NotImplementedException();
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			items.CopyTo(array, arrayIndex);
		}

		public override int GetHashCode()
		{
			return hashCode;
		}

		public override bool Equals(object other)
		{
			return Equals(other as HashedList<T>);
		}

		private bool Equals(HashedList<T> other)
		{
			// Follows Item 6 in Effective C# in first three tests.

			if (object.ReferenceEquals(other, null))
			{
				return false;
			}

			if (object.ReferenceEquals(this, other))
			{
				return true;
			}

			if (GetType() != other.GetType())
			{
				return false;
			}

			if (hashCode != other.hashCode)
			{
				// Can't be equal if they have different hash codes.
				return false;
			}

			if (items.Count != other.items.Count)
			{
				// Can't be equal if they contain a different number of items.
				return false;
			}

			for (int i = 0; i < items.Count; i++)
			{
				if (!object.Equals(items[i], other.items[i]))
				{
					// The other list doesn't contain this item so they can't be equal.
					return false;
				}
			}

			// No differences found.
			return true;
		}

		public IEnumerator<T> GetEnumerator()
		{
			return items.GetEnumerator();
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return ((IEnumerable)items).GetEnumerator();
		}

		public static bool operator ==(HashedList<T> list1, HashedList<T> list2)
		{
			return object.Equals(list1, list2);
		}

		public static bool operator !=(HashedList<T> list1, HashedList<T> list2)
		{
			return !(list1 == list2);
		}

		public T this[int index]
		{
			get
			{
				return items[index];
			}
			set
			{
				throw new InvalidOperationException();
			}
		}

		public int Count
		{
			get
			{
				return items.Count;
			}
		}

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}
	}
}
